A "pure" recursive solution passes information down through parameters.
- We add an extra parameter, succ_candidate, to track the best successor found so far.
- If key < node.key, the current node is a potential successor. We update our candidate to node.key and search LEFT to find an even better (smaller) successor.
- If key >= node.key, the current node is too small. It cannot be a successor. We must search RIGHT for a larger key, without changing the candidate.
- Base Case: When node is None, the search ends, and we return the best candidate found along the path.
A Deeper Look
This approach combines both "cases" from the iterative method. The succ_candidate automatically handles the ancestor case. If the code finds the node for the key and needs to search its right subtree, this logic will also naturally find the minimum value there.
def successor(node, key, succ_candidate=None):
# Base Case: Run out of nodes, return best so far.
if node is None:
return succ_candidate
if key < node.key:
# Potential successor. Search LEFT for a better one.
return successor(__________, key, succ_candidate=__________)
else: # key >= node.key
# Not a successor. Must search RIGHT.
return successor(__________, key, succ_candidate)
def predecessor(node, key, pred_candidate=None):
# Base Case:
if node is None:
return __________
if key > node.key:
# Potential predecessor. Search RIGHT for better.
return predecessor(__________, key, pred_candidate=__________)
else: # key <= node.key
# Not a predecessor. Must search LEFT.
return predecessor(__________, key, pred_candidate)
Copied!